package main

import "strings"

// 22. 括号生成
func main() {
	n := 2
	res := generateParenthesis(n)
	for _, l := range res {
		println(l)
	}
}

func generateParenthesis(n int) []string {
	const leftStr, rightStr = "(", ")"
	var res []string
	var stringSet []string

	var dfs func(leftNum, rightNum int)
	dfs = func(leftNum, rightNum int) {
		if leftNum == n && rightNum == n {
			res = append(res, strings.Join(stringSet, ""))
		}
		// 当前状态只有加左 或者加 右
		if leftNum < n { // leftNum没加完就可以一直加左边
			stringSet = append(stringSet, leftStr)
			dfs(leftNum+1, rightNum)
			stringSet = stringSet[:len(stringSet)-1]
		}
		if rightNum < n && leftNum > rightNum { // rightNum没加完且左边大于右边，可以加
			stringSet = append(stringSet, rightStr)
			dfs(leftNum, rightNum+1)
			stringSet = stringSet[:len(stringSet)-1]
		}
	}
	dfs(0, 0)
	return res
}

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
//示例 1：
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//示例 2：
//
//输入：n = 1
//输出：["()"]
//
//
//提示：
//
//1 <= n <= 8
